package libnetdb.dm.assoc.dhp;
import java.util.*;

import libnetdb.dm.assoc.base.*;




public class CandidateGenerator {
    public CandidateGenerator() {}

    private boolean prefix_check(Litemset a, Litemset b){
        for(int i=0;i<a.size()-1;i++)
            if(a.ids[i]!=b.ids[i]) return false;
        return true;
    }

    private int compare(Litemset itemset, int ids[]){
        for(int i=0;i<itemset.size();i++)
            if(itemset.ids[i]!=ids[i]) return itemset.ids[i]-ids[i];
        return 0;
    }

    protected int binarySearch(Litemset c[], int ids[]){
        int start = 0, end = c.length-1;
        for(int x=(start+end)/2; start<=end; x=(start+end)/2){
            int rc = compare(c[x], ids);
            if(rc < 0)  start = x + 1;
            else if(rc > 0) end = x - 1;
            else return x;
        }
        return -1;
    }

    private boolean checkCandidate(Litemset c[], int ids[]){
        int id = ids[0], tmp;
//        boolean flag = true;
        for(int i=0;i<ids.length-1;i++) ids[i] = ids[i+1];
        for(int i=0;i<ids.length;i++){
            if(i < ids.length - 2 && binarySearch(c, ids)==-1) return false;
            tmp = id; id = ids[i]; ids[i] = tmp; // swap(ids[i],id)
        }
        return true;
    }

    private void addCandidate(
            Litemset c[], int start_idx, int end_idx, Collection set, HashPruner pruner
            ){
        int k = c[0].size(), ids[] = new int[k+1];
        for(int i=start_idx;i<end_idx;i++)
            for(int j=i+1;j<=end_idx;j++){
        for(int t=0; t<k; t++) ids[t] = c[i].ids[t];
        ids[k] = c[j].ids[k-1];
        if(checkCandidate(c, ids) && pruner.check(ids))
            set.add(new Litemset(ids, 0));
            }
    }

    public Litemset[] generate(Litemset c[], HashPruner pruner){
        int start_idx = 0;
        Collection set = new ArrayList();
        for(int i=1;i<c.length;i++)
            if(!prefix_check(c[start_idx], c[i])){
        addCandidate(c, start_idx, i-1, set, pruner);
        start_idx = i;
            }
            if(c.length>0) addCandidate(c, start_idx, c.length-1, set, pruner);
            return (Litemset[]) set.toArray(new Litemset[0]);
    }
}